package com.fyl.basic_algorithm.linkedList;

/**
 * @author 冯永龙
 * @date 2021/3/12 20:53
 */
public class SinglyLinkedList {
    private Node head = null;

    public Node findByValue(int value) {
        Node p = head;
        while (p != null && p.getData() != value) {
            p = p.getNext();
        }

        return p;
    }

    public Node findByIndex(int index) {
        Node p = head;
        int pos = 0;
        while (p != null && pos != index) {
            p = p.getNext();
            ++pos;
        }
        return p;
    }

    /**
     * 无头结点，表头部插入，用于将输入的顺序相反，逆序
     *
     * @param value
     */
    public void insertToHead(int value) {
        Node newNode = new Node(value, null);
        insertToHead(newNode);
    }

    public void insertToHead(Node newNode) {
        if (head == null) {
            head = newNode;
        } else {
            newNode.setNext(head);
            head = newNode;
        }
    }

    /**
     * 顺序插入，链表尾部插入
     *
     * @param value
     */
    public void insertTail(int value) {
        Node node = new Node(value, null);
        if (head == null) {
            head = node;
        } else {
            Node p = head;
            while (p.getNext() != null) {
                p = p.getNext();
            }
//            node.setNext(p);
            p.setNext(node);
        }
    }

    /**
     * 插入某个元素之后
     *
     * @param p
     * @param value
     */
    public void insertAfter(Node p, int value) {
        Node newNode = new Node(value, null);
        insertAfter(p, newNode);
    }

    public void insertAfter(Node p, Node newNode) {
        if (p == null) return;

        newNode.setNext(p.getNext());
        p.setNext(newNode);
    }

    /**
     * 插入某个元素之前
     *
     * @param p
     * @param value
     */
    public void insertBefore(Node p, int value) {
        Node newNode = new Node(value, null);

    }

    public void insertBefore(Node p, Node newNode) {
        if (p == null) return;
        if (head == p) {
            insertToHead(newNode);
            return;
        }

        Node q = head;
        while (q != null && q.getNext() != p) {
            q = q.getNext();
        }

        if (q == null) return;

        newNode.setNext(q.getNext());
        q.setNext(newNode);
    }

    public void deleteByNode(Node p) {
        if (p == null || head == null) return;

        if (p == head) {
            head = head.getNext();
            return;
        }

        Node q = head;
        while (q != null && q.getNext() != p) {
            q = q.getNext();
        }

        if (q == null) return;

        q.setNext(q.getNext().getNext());
    }

    public void deleteByValue(int value) {
        if (head == null) return;

        Node p = head;
        Node q = null; // 记录p的前驱
        while (p != null || p.getData() != value) {
            q = p;
            p = p.getNext();
        }

        if (p == null) return;

        if (q == null) {
            head = head.getNext();  //元素为头结点的情况
        } else {
            q.setNext(q.getNext().getNext());
        }


    }

    /**
     * 可重复删除指定value代码
     *
     * @param value
     */
    public void deleteRepeatValue(int value) {
        if (head != null && head.getData() == value) {
            head = head.getNext();
        }

        Node node = head;
        while (node != null) {
            if (node.getNext().getData() == value) {
                node.setNext(node.getNext().getNext());
            }
            node = node.getNext();
        }
    }

    public void printAll() {
        Node node = head;
        while (node != null) {
            System.out.print(node.getData() + " ");
            node = node.getNext();
        }
        System.out.println();
    }

    /**
     * 带头结点的链表翻转
     *
     * @param p
     * @return
     */
    public Node inverseLinkList_head(Node p) {
        // Head 为新建的一个头结点
        Node Head = new Node(999, null);
        // p为原来整个链表的头部，现在Head指向整个链表
        Head.setNext(p);
        //带头结点的链表翻转等价于从第二个元素开始重新头插法建立链表
        Node Cur = p.getNext();
        p.setNext(null);
        Node next = null;

        //设置一个中间节点Cur用于保存将要反转的节点在赋值给Head
        while (Cur != null) {
            next = Cur.getNext();
            Cur.setNext(Head.getNext());
            Head.setNext(Cur);
            System.out.println("first " + Head.getData());
            Cur = next;
        }

        //返回左半部分的中间之前的那个节点，从此处开始同步向两边比较
        return Head;
    }

    /**
     * 无头结点的链表翻转
     *
     * @param p
     * @return
     */
    public Node inverseLinkList(Node p) {
        Node pre = null;  //储存逆序的链表
        Node r = head;
        Node next = null;

        while (r != p) {
            next = r.getNext();
            //相当于头插法，将r的第一个节点插入pre中
            r.setNext(pre);
            pre = r;
            r = next;
        }

        r.setNext(pre);
        //　返回左半部分的中点之前的那个节点
        //　从此处开始同步像两边比较
        return r;
    }

    public boolean palindrome() {
        if (head == null) {
            return false;
        } else {
            System.out.println("开始寻找中间节点");
            Node p = head;
            Node q = head;
            if (p.getNext() == null) {
                System.out.println("只有一个元素");
                return true;
            }

            while (q.getNext() != null && q.getNext().getNext() != null) {
                p = p.getNext();
                q = q.getNext().getNext();
            }

            System.out.println("中间节点" + p.getData());
            System.out.println("开始执行奇数节点的回文判断");
            Node leftLink = null;
            Node rightLink = null;
            if (q.getNext() == null) {
                //p一定为奇数节点的中心，且节点数目为奇数
                rightLink = p.getNext();
                leftLink = inverseLinkList(p).getNext();
                System.out.println("左边第一个节点" + leftLink.getData());
                System.out.println("右边第一个节点" + rightLink.getData());
            } else {
                //p，q皆为中点
                rightLink = p.getNext();
                leftLink = inverseLinkList(p);
            }
            return TFResult(leftLink,rightLink);
        }
    }

    public boolean TFResult(Node left, Node right) {
        Node l = left;
        Node r = right;

        boolean flag = true;
        System.out.println("left_:" + l.getData());
        System.out.println("right_:" + r.getData());
        while (l != null && r != null) {
            if (l.getData() == r.getData()) {
                l = l.getNext();
                r = r.getNext();
            } else {
                flag = false;
                break;
            }
        }

        System.out.println("什么结果：");
        return flag;
    }

    public static void main(String[] args) {

        SinglyLinkedList link = new SinglyLinkedList();
        System.out.println("hello");
        //int data[] = {1};
        //int data[] = {1,2};
        //int data[] = {1,2,3,1};
        //int data[] = {1,2,5};
        //int data[] = {1,2,2,1};
        // int data[] = {1,2,5,2,1};
        int data[] = {1, 2, 5, 3, 1};

        for (int i = 0; i < data.length; i++) {
            //link.insertToHead(data[i]);
            link.insertTail(data[i]);
        }
        // link.printAll();
        // Node p = link.inverseLinkList_head(link.head);
        // while(p != null){
        //     System.out.println("aa"+p.data);
        //     p = p.next;
        // }

        System.out.println("打印原始:");
        link.printAll();
        if (link.palindrome()) {
            System.out.println("回文");
        } else {
            System.out.println("不是回文");
        }
    }
}

class Node {
    private int data;
    private Node next;

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}
